| 翻訳と辞書 |
| Tutte embedding ： ウィキペディア英語版 |
Tutte embedding
In graph drawing and geometric graph theory, a Tutte embedding or barycentric embedding of a simple 3-vertex-connected planar graph is a crossing-free straight-line embedding with the properties that the outer face is a convex polygon and that each interior vertex is at the average (or barycenter) of its neighbor's positions. If the outer polygon is fixed, this condition on the interior vertices determines their position uniquely as the solution to a system of linear equations. Solving the equations geometrically produces a planar embedding. Tutte's spring theorem, proven by , states that this unique solution is always crossing-free, and more strongly that every face of the resulting planar embedding is convex.〔.〕 It is called the spring theorem because such an embedding can be found as the equilibrium position for a system of springs representing the edges of the graph.
==Example==
Let ''G'' be the graph of a cube, and (selecting one of its quadrilateral faces as the outer face) fix the four vertices of the outer face at the four corners of a unit square, the points whose ''x'' and ''y'' coordinates are all four combinations of zero and one.
Then, if the remaining four vertices are placed at the four points whose ''x'' and ''y'' coordinates are combinations of 1/3 and 2/3, as in the figure, the result will be a Tutte embedding. For, at each interior vertex ''v'' of the embedding, and for each of the two coordinates, the three neighbors of ''v'' have coordinate values that are equal to ''v'', smaller by 1/3, and larger by 1/3; the average of these values is the same as the coordinate value of ''v'' itself.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「Tutte embedding」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|